//----------------------------------------------------------------------数论基础
#define swap(a,b) do{a=a^b;b=a^b;a=a^b;}while(0)
typedef long long LL;
LL gcd(LL a,LL b)
{
	while(b){swap(a,b);b=b%a;}
	return a>0?a:-a;
}
void ext_gcd(LL a,LL b,LL *d,LL *x,LL *y)
{
	if(b==0){*d=a;*x=1;*y=0;return;}
	ext_gcd(b,a%b,d,y,x);
	*y-=a/b**x;
}
LL mod_mult(LL a,LL b,LL mo)//ret:a*b%mo
{
	LL ret;
	a%=mo;
	for(ret=0;b;a=(a<<1)%mo,b>>=1)
		if(b&1)
			ret=(ret+a)%mo;
	return ret;
}
LL mod_exp(LL a,LL b,LL mo)//ret:a^b%mo
{
	LL ret=1,temp=a%mo;
	for(;b;b>>=1,temp=mod_mult(temp,temp,mo))
		if(b&1)
			ret=mod_mult(ret,temp,mo);
	return ret;
}
